package chapter02.utils;

public class List<T> {
	private int size = 0;
	private Node<T> first;
	private Node<T> last;
	public List(){
	}
	public boolean isEmpty(){
		return size > 0;
	}
	/**
	 * 在末尾添加元素
	 * @param item 待添加的元素
	 * @return
	 */
	public boolean add(T item){
		return linkLast(item);
	}
	/**
	 * 在index出添加元素
	 * @param index
	 * @param item
	 * @return
	 */
	public boolean add(int index,T item){
		checkPositionIndex(index);
		if(index == size){
			return linkLast(item);
		}else{
			return linkBefore(item,node(index));
		}
	}
	/**
	 * 判断index是否是合适的
	 * @param index
	 * @return
	 */
	private boolean isElementIndex(int index){
		return index>=0 && index <=size;
	}
	/**
	 * 越界信息
	 * @param index
	 * @return
	 */
	private String outOfBoundMsg(int index){
		return "Index: "+index +", Size: "+size;
	}
	/**
	 * 检查位置信息，
	 * @param index
	 */
	private void checkPositionIndex(int index) {
		if(!isElementIndex(index))
			throw new IndexOutOfBoundsException(outOfBoundMsg(index));
	}
	private boolean linkBefore(T item, Node<T> node) {
		//assert node != null
		Node<T> prev = node.prev;
		Node<T> newNode = new Node<T>(item,prev,node);
		node.prev = newNode;
		if(prev == null){ //如果是添加在list头，则node为当前list的头，first.prev = null,需要更新first
			first = newNode;
		}else{ //否则的话，保证双向链表正常工作，需要完善附近的node
			prev.next = newNode;
		}
		return true;
	}
	private boolean linkLast(T item) {
		Node<T> l = last;
		Node<T> node = new Node<T>(item, l, null);
		last = node;
		if(l == null){
			first = node;
		}else{
			l.next = node;
		}
		size++;
		return true;
	}
	/**
	 * 找到index位置的node
	 * @param index
	 * @return
	 */
	private Node<T> node(int index) {
		Node<T> node;
		if(index > (size >> 1)){
			node = last;
			int i = 1;
			while(size - i++ > index){
				node = node.prev;
			}
		}else{
			node = first;
			int i = 0;
			while(i++ < index){
				node = node.next;
			}
		}
		return node;
	}


	class Node<T>{
		T elem;
		Node<T> prev;
		Node<T> next;
		public Node(T elem, Node<T> prev, Node<T> next) {
			super();
			this.elem = elem;
			this.prev = prev;
			this.next = next;
		}
		@Override
		public String toString() {
			return "Node [elem=" + elem + "]";
		}
	}
	public int size() {
		return size;
	}
	public T get(int i) {
		Node<T> node = node(i);
		return node.elem;
	}
}
